/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2019年05月08日
*   描    述：
*   Copyright (C) 2019 All rights reserved.
*   
================================================================*/


#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int rob(vector<int>& nums) {
        int size = nums.size();
        if(size == 0)
            return 0;

        vector<int> dp(size+1, 0);
        dp[size - 1] = nums[size - 1];
        
        for(int i = size - 2; i >= 0; i--){
            if(nums[i] + dp[i+2] > dp[i+1]){
                dp[i] = nums[i] + dp[i+2];
            }else{
                dp[i] = dp[i+1];
            }
        }

        return dp[0];
    }
    
};

class Solution {
public:
    int rob(vector<int>& nums) {
        int size = nums.size();
        if(size == 0)
            return 0;
        
        int lastval = 0;
        int now = nums[size - 1];
        int tmp = 0;

        for(int i = size - 2; i >= 0; i--){
            if(nums[i] + lastval > now){
                tmp = now;
                now = nums[i] + lastval;
                lastval = tmp;
            }else{
                lastval = now;
            }
        }

        return now;
    }
};


